cf_1783b_Matrix of Differences
题意
对于一个n * n的矩阵，计算每一个相邻的数字之差的绝对值，输出绝对值覆盖范围最广的方案。
例如当 n = 2
::: tips
|1 - 4| = 3、 |1 - 3| = 2、 |3 - 2| = 1、 |4 - 2| = 2。1 2 3 都有，是最佳方案。
:::
分析
猜一下结论，最好的方案绝对值必然从[1, - 1]都有。
所以1和必须挨着。不然 - 1无法产生。
接下来就毫无思路了😔
看题解
找规律题。
有一种办法感觉跟我稍微想到了一点儿。就是一个小一个大，例如n = 3。第一行从左往右1 9 2，第二行从右向左8 3 7，第三行从左向右 4 6 5，就是一个蛇形矩阵。
原理是：最大程度的充分接触.|1 - | = - 1， | - 2| = - 2， | 2 - ( -1) | = - 3 ……以此类推，这条贪吃蛇共有8条线，产生了要求的8个数字。
规律有了，代码就好写了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include<iostream>
#include<cstring>
#include<algorithm>
#include<string.h>
#pragma GCC optimize("Ofast")
#define DE() cout << "OK" << endl;
#define EDL() cout << endl;
#define FASTIO \
ios ::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const int N = 110;
#define n2 n * n
int T, n, num;
int a[N][N];
int mai, maxn, minn;
void init()
{
cin >> T;
}
void Num()
{
if(mai == 2)
{
minn ++;
num = maxn;
}
else
{
maxn --;
num = minn;
}
mai = 3 - mai;
}
void solve()
{
num = 1;
int j = 1, i = 1;
int lr = 2;
mai = 2, maxn = n2, minn = 1;
while(num <= n2)
{
if(lr == 2)
{
while(j <= n && num <= n2)
{
a[i][j] = num;
Num();
j ++;
}
}
else if(lr == 1)
{
while(j >= 1 && num <= n2)
{
a[i][j] = num;
Num();
j --;
}
}
if(lr == 2 && num <= n2)
{
j --;
i ++;
}
if(lr == 1 && num <= n2)
{
i ++;
j ++;
}
lr = 3 - lr;
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
cout << a[i][j] << " ";
}
EDL()
}
}
int main()
{
FASTIO
init();
while(T --)
{
cin >> n;
solve();
}
return 0;
}
|